// 经典动态规划：0-1 背包问题
// 后台天天有人问背包问题，这个问题其实不难啊，如果我们号动态规划系列的十几篇文章你都看过，借助框架，遇到背包问题可以说是手到擒来好吧。无非就是状态 + 选择，也没啥特别之处嘛。
// 今天就来说一下背包问题吧，就讨论最常说的 0-1 背包问题。描述：
// 给你一个可装载重量为 W 的背包和 N 个物品，每个物品有重量和价值两个属性。其中第 i 个物品的重量为 wt[i]，价值为 val[i]，现在让你用这个背包装物品，最多能装的价值是多少？
// 举个简单的例子，输入如下：
// N = 3, W = 4
// wt = [2, 1, 3]  val = [4, 2, 3]
// 算法返回 6，选择前两件物品装进背包，总重量 3 小于 W，可以获得最大价值 6。
// 题目就是这么简单，一个典型的动态规划问题。这个题目中的物品不可以分割，要么装进包里，要么不装，不能说切成两块装一半。这就是 0-1 背包这个名词的来历。
// 解决这个问题没有什么排序之类巧妙的方法，只能穷举所有可能，根据我们「动态规划详解」中的套路，直接走流程就行了。
// 动规标准套路
// 看来我得每篇动态规划文章都得重复一遍套路，历史文章中的动态规划问题都是按照下面的套路来的。
// 第一步要明确两点，「状态」和「选择」。
// 先说状态，如何才能描述一个问题局面？只要给几个物品和一个背包的容量限制，就形成了一个背包问题呀。所以状态有两个，就是「背包的容量」和「可选择的物品」。
// 再说选择，也很容易想到啊，对于每件物品，你能选择什么？选择就是「装进背包」或者「不装进背包」嘛。
// 明白了状态和选择，动态规划问题基本上就解决了，只要往这个框架套就完事儿了

// for 状态1 in 状态1的所有取值：
//     for 状态2 in 状态2的所有取值：
//         for ...
//             dp[状态1][状态2][...] = 择优(选择1，选择2...)
// PS：此框架出自历史文章 团灭 LeetCode 股票问题。
// 第二步要明确 dp 数组的定义。
// 首先看看刚才找到的「状态」，有两个，也就是说我们需要一个二维 dp 数组。
// dp[i][w] 的定义如下：对于前 i 个物品，当前背包的容量为 w，这种情况下可以装的最大价值是 dp[i][w]。
// 比如说，如果 dp[3][5] = 6，其含义为：对于给定的一系列物品中，若只对前 3 个物品进行选择，当背包容量为 5 时，最多可以装下的价值为 6。
// PS：为什么要这么定义？便于状态转移，或者说这就是套路，记下来就行了。建议看一下我们的动态规划系列文章，几种套路都被扒得清清楚楚了。
// 根据这个定义，我们想求的最终答案就是 dp[N][W]。base case 就是 dp[0][..] = dp[..][0] = 0，因为没有物品或者背包没有空间的时候，能装的最大价值就是 0。
// 细化上面的框架：
// int dp[N+1][W+1]
// dp[0][..] = 0
// dp[..][0] = 0

// for i in [1..N]:
//     for w in [1..W]:
//         dp[i][w] = max(
//             把物品 i 装进背包,
//             不把物品 i 装进背包
//         )
// return dp[N][W]
//第三步，根据「选择」，思考状态转移的逻辑。
// 简单说就是，上面伪码中「把物品 i 装进背包」和「不把物品 i 装进背包」怎么用代码体现出来呢？
// 这就要结合对 dp 数组的定义和我们的算法逻辑来分析了：
// 先重申一下刚才我们的 dp 数组的定义：
// dp[i][w] 表示：对于前 i 个物品，当前背包的容量为 w 时，这种情况下可以装下的最大价值是 dp[i][w]。
// 如果你没有把这第 i 个物品装入背包，那么很显然，最大价值 dp[i][w] 应该等于 dp[i-1][w]，继承之前的结果。
// 如果你把这第 i 个物品装入了背包，那么 dp[i][w] 应该等于 dp[i-1][w - wt[i-1]] + val[i-1]。
// 首先，由于 i 是从 1 开始的，所以 val 和 wt 的索引是 i-1 时表示第 i 个物品的价值和重量。
// 而 dp[i-1][w - wt[i-1]] 也很好理解：你如果装了第 i 个物品，就要寻求剩余重量 w - wt[i-1] 限制下的最大价值，加上第 i 个物品的价值 val[i-1]。
// 综上就是两种选择，我们都已经分析完毕，也就是写出来了状态转移方程，可以进一步细化代码：
// for i in [1..N]:
//     for w in [1..W]:
//         dp[i][w] = max(
//             dp[i-1][w],
//             dp[i-1][w - wt[i-1]] + val[i-1]
//         )
// return dp[N][W]

// 最后一步，把伪码翻译成代码，处理一些边界情况。
// 我用 C++ 写的代码，把上面的思路完全翻译了一遍，并且处理了 w - wt[i-1] 可能小于 0 导致数组索引越界的问题
// 至此，背包问题就解决了，相比而言，我觉得这是比较简单的动态规划问题，因为状态转移的推导比较自然，基本上你明确了 dp 数组的定义，就可以理所当然地确定状态转移了。
const knapsack = (W: number, N: number, wt: number[], val: number[]) => {
  const dp: number[][] = []
  for (let i = 1; i <= N; i++) {
    for (let w = 1; w <= W; w++) {
      if (w - wt[i - 1] < 0) {
        dp[i][w] = dp[i - 1][w]
      } else {
        dp[i][w] = Math.max(dp[i - 1][w - wt[i - 1]] + val[i - 1], dp[i - 1][w])
      }
    }
  }
  return dp[N][W];
}

// 经典动态规划：完全背包问题

// 零钱兑换 2 是另一种典型背包问题的变体，我们前文已经讲了 经典动态规划：0-1 背包问题 和 背包问题变体：相等子集分割。
// 文聊的是 LeetCode 第 518 题 Coin Change 2，题目如下：
// 给定不同面额的硬币和一个总金额，写出函数计算出可以凑出总金额的硬币组合，假设每种面额无限
// amount = 5 coisn = [1,2,5]
// 输出 4
// 我们可以把这个问题转化为背包问题的描述形式：
// 有一个背包，最大容量为 amount，有一系列物品 coins，每个物品的重量为 coins[i]，每个物品的数量无限。请问有多少种方法，能够把背包恰好装满？
// 这个问题和我们前面讲过的两个背包问题，有一个最大的区别就是，每个物品的数量是无限的，这也就是传说中的「完全背包问题」，没啥高大上的，无非就是状态转移方程有一点变化而已。
// 下面就以背包问题的描述形式，继续按照流程来分析。
// 解题思路
// 第一步要明确两点，「状态」和「选择」。
// 状态有两个，就是「背包的容量」和「可选择的物品」，选择就是「装进背包」或者「不装进背包」嘛，背包问题的套路都是这样。
// 明白了状态和选择，动态规划问题基本上就解决了，只要往这个框架套就完事儿了：
// for 状态1 in 状态1的所有取值：
//     for 状态2 in 状态2的所有取值：
//         for ...
//             dp[状态1][状态2][...] = 计算(选择1，选择2...)
// 第二步要明确 dp 数组的定义。
// 首先看看刚才找到的「状态」，有两个，也就是说我们需要一个二维 dp 数组。
// dp[i][j] 的定义如下：
// 若只使用前 i 个物品，当背包容量为 j 时，有 dp[i][j] 种方法可以装满背包。
// 换句话说，翻译回我们题目的意思就是：
// 若只使用 coins 中的前 i 个硬币的面值，若想凑出金额 j，有 dp[i][j] 种凑法。
// 经过以上的定义，可以得到：
// base case 为 dp[0][..] = 0， dp[..][0] = 1。因为如果不使用任何硬币面值，就无法凑出任何金额；如果凑出的目标金额为 0，那么“无为而治”就是唯一的一种凑法。
// 我们最终想得到的答案就是 dp[N][amount]，其中 N 为 coins 数组的大小。
// 大致的伪码思路如下：
// int dp[N+1][amount+1]
// dp[0][..] = 0
// dp[..][0] = 1

// for i in [1..N]:
//     for j in [1..amount]:
//         把物品 i 装进背包,
//         不把物品 i 装进背包
// return dp[N][amount]

// 第三步，根据「选择」，思考状态转移的逻辑。
// 注意，我们这个问题的特殊点在于物品的数量是无限的，所以这里和之前写的背包问题文章有所不同。
// 如果你不把这第 i 个物品装入背包，也就是说你不使用 coins[i] 这个面值的硬币，那么凑出面额 j 的方法数 dp[i][j] 应该等于 dp[i-1][j]，继承之前的结果。
// 如果你把这第 i 个物品装入了背包，也就是说你使用 coins[i] 这个面值的硬币，那么 dp[i][j] 应该等于 dp[i][j-coins[i-1]]。
// 首先由于 i 是从 1 开始的，所以 coins 的索引是 i-1 时表示第 i 个硬币的面值。
// dp[i][j-coins[i-1]] 也不难理解，如果你决定使用这个面值的硬币，那么就应该关注如何凑出金额 j - coins[i-1]。
// 比如说，你想用面值为 2 的硬币凑出金额 5，那么如果你知道了凑出金额 3 的方法，再加上一枚面额为 2 的硬币，不就可以凑出 5 了嘛。
// 综上就是两种选择，而我们想求的 dp[i][j] 是「共有多少种凑法」，所以 dp[i][j] 的值应该是以上两种选择的结果之和：

// for (int i = 1; i <= n; i++) {
//   for (int j = 1; j <= amount; j++) {
//       if (j - coins[i-1] >= 0)
//           dp[i][j] = dp[i - 1][j] 
//                    + dp[i][j-coins[i-1]];
// return dp[N][W]

// 最后一步，把伪码翻译成代码，处理一些边界情况。
// 我用 Java 写的代码，把上面的思路完全翻译了一遍，并且处理了一些边界问题：
const change = (amount: number[], coins: number[]) => {
  let n = coins.length;
  let dp: number[][] = []
  // base case
  for (let i = 0; i <= n; i++)
    dp[i][0] = 1;

  for (let i = 1; i <= n; i++) {
    for (let j = 1; j <= amount.length; j++)
      if (j - coins[i - 1] >= 0)
        dp[i][j] = dp[i - 1][j]
          + dp[i][j - coins[i - 1]];
      else
        dp[i][j] = dp[i - 1][j];
  }
  return dp[n][amount.length];
}
// 而且，我们通过观察可以发现，dp 数组的转移只和 dp[i][..] 和 dp[i-1][..] 有关，所以可以压缩状态，进一步降低算法的空间复杂度：
const change2 = (amount: number[], coins: number[]) => {
  let n = coins.length;
  let dp: number[] = new Array(amount.length);
  dp[0] = 1; // base case
  for (let i = 0; i < n; i++)
    for (let j = 1; j <= amount.length; j++)
      if (j - coins[i] >= 0)
        dp[j] = dp[j] + dp[j - coins[i]];

  return dp[amount.length];
}

// 这个解法和之前的思路完全相同，将二维 dp 数组压缩为一维，时间复杂度 O(N*amount)，空间复杂度 O(amount)。
// 至此，这道零钱兑换问题也通过背包问题的框架解决了。
